import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution767 {
    public String reorganizeString(String s) {
        int[] f=new int[26];
        for (char task : s.toCharArray()) {
            f[task-'a']++;
        }
        PriorityQueue<int[]> priorityQueue=new PriorityQueue<>((a, b)->b[1]-a[1]);
        for (int i=0;i<26;i++){
            if (f[i]>0){
                priorityQueue.offer(new int[]{i,f[i]});
            }
        }
        StringBuilder stringBuilder=new StringBuilder();
        Queue<int[]> waiting=new LinkedList<>();
        int cur=0;
        while (!priorityQueue.isEmpty() || !waiting.isEmpty()){
            cur++;
            while (!waiting.isEmpty() && cur-waiting.peek()[2]>1){
                int[] p=waiting.poll();
                priorityQueue.offer(new int[]{p[0],p[1]});
            }
            if (!priorityQueue.isEmpty()) {
                int[] p = priorityQueue.poll();
                stringBuilder.append((char)(p[0]+'a'));
                if (p[1] - 1 > 0) {
                    waiting.offer(new int[]{p[0], p[1] - 1,cur});
                }
            }else{
                return "";
            }
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution767().reorganizeString("aab"));
    }
}
